<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
      <title>GTL - Graph Template Library: bin_heap.h Source File</title>
      <link href="doxygen.css" rel="stylesheet" type="text/css">
  </head>
  <body>
    <p class="links">  
      <a href="../index.html">Home</a> |
      Documentation |
      <a href="../register.html">Download</a> |
      <a href="../platforms.html">Platforms</a> |
      <a href="../refer.html">Projects</a> |      
      <a href="../lists.html">Mailing Lists</a> |
      <a href="../history.html">Version History</a>
    </p>

<!-- Generated by Doxygen 1.5.3 -->
<div class="tabs">
  <ul>
    <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
    <li><a href="classes.html"><span>Classes</span></a></li>
    <li class="current"><a href="files.html"><span>Files</span></a></li>
    <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
  </ul>
</div>
<h1>bin_heap.h</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">//==========================================================================</span>
<a name="l00002"></a>00002 <span class="comment">//</span>
<a name="l00003"></a>00003 <span class="comment">//   bin_heap.h</span>
<a name="l00004"></a>00004 <span class="comment">//</span>
<a name="l00005"></a>00005 <span class="comment">//==========================================================================</span>
<a name="l00006"></a>00006 <span class="comment">// $Id: bin_heap.h,v 1.10 2003/01/07 07:01:05 chris Exp $</span>
<a name="l00007"></a>00007 
<a name="l00008"></a>00008 <span class="preprocessor">#ifndef GTL_BIN_HEAP_H</span>
<a name="l00009"></a>00009 <span class="preprocessor"></span><span class="preprocessor">#define GTL_BIN_HEAP_H</span>
<a name="l00010"></a>00010 <span class="preprocessor"></span>
<a name="l00011"></a>00011 <span class="preprocessor">#include &lt;GTL/GTL.h&gt;</span>
<a name="l00012"></a>00012 
<a name="l00013"></a>00013 <span class="preprocessor">#include &lt;cassert&gt;</span>
<a name="l00014"></a>00014 <span class="preprocessor">#include &lt;vector&gt;</span>
<a name="l00015"></a>00015 <span class="preprocessor">#include &lt;map&gt;</span>
<a name="l00016"></a>00016 
<a name="l00017"></a>00017 __GTL_BEGIN_NAMESPACE
<a name="l00018"></a>00018 
<a name="l00023"></a>00023 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00024"></a>00024 <span class="keyword">class </span>heap_node
<a name="l00025"></a>00025 {
<a name="l00026"></a>00026 <span class="keyword">public</span>:
<a name="l00031"></a>00031     heap_node()
<a name="l00032"></a>00032     {
<a name="l00033"></a>00033     }
<a name="l00034"></a>00034 
<a name="l00038"></a>00038     heap_node(<span class="keyword">const</span> T&amp; n) : data(n)
<a name="l00039"></a>00039     {
<a name="l00040"></a>00040     }
<a name="l00041"></a>00041 
<a name="l00046"></a>00046     T data;
<a name="l00047"></a>00047 
<a name="l00052"></a>00052     <span class="keywordtype">int</span> pos;
<a name="l00053"></a>00053 };
<a name="l00054"></a>00054 
<a name="l00055"></a>00055     
<a name="l00061"></a>00061 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00062"></a><a class="code" href="a00006.html">00062</a> <span class="keyword">class </span><a class="code" href="a00006.html" title="Binary heap.">bin_heap</a>
<a name="l00063"></a>00063 {
<a name="l00064"></a>00064 <span class="keyword">public</span>:
<a name="l00070"></a>00070     <a class="code" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd" title="Creates empty binary heap.">bin_heap</a>(<span class="keyword">const</span> Pred&amp; prd);
<a name="l00071"></a>00071 
<a name="l00078"></a>00078     <a class="code" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd" title="Creates empty binary heap.">bin_heap</a>(<span class="keyword">const</span> Pred&amp; prd, <span class="keyword">const</span> <span class="keywordtype">int</span> est_size);
<a name="l00079"></a>00079 
<a name="l00085"></a>00085     <a class="code" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd" title="Creates empty binary heap.">bin_heap</a>(<span class="keyword">const</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;</a>&amp; bh);
<a name="l00086"></a>00086 
<a name="l00097"></a>00097     <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;</a>&amp; <a class="code" href="a00006.html#d31b6806316a272686015fcbf5f633cd" title="Assigns bh to this binary heap.">operator=</a>(<span class="keyword">const</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;</a>&amp; bh);
<a name="l00098"></a>00098     
<a name="l00102"></a>00102     <a class="code" href="a00006.html#5283db56783a84ee28dea9d393acf905" title="Destructor.">~bin_heap</a>();
<a name="l00103"></a>00103 
<a name="l00109"></a>00109     <span class="keywordtype">void</span> <a class="code" href="a00006.html#6d658d61533e66cf83dce2f8e35bed17" title="Inserts ins in heap.">push</a>(<span class="keyword">const</span> T&amp; ins);
<a name="l00110"></a>00110 
<a name="l00114"></a>00114     <span class="keywordtype">void</span> <a class="code" href="a00006.html#b463bc655b2f46cd5ff021cab28b1210" title="Removes the element on top of the heap.">pop</a>();
<a name="l00115"></a>00115 
<a name="l00121"></a>00121     <span class="keyword">const</span> T&amp; <a class="code" href="a00006.html#09924a9669f054bc6fdcf2dc5637f7f3" title="Returns a reference to the element at the top of the heap.">top</a>() <span class="keyword">const</span>;
<a name="l00122"></a>00122     
<a name="l00135"></a>00135     <span class="keywordtype">void</span> <a class="code" href="a00006.html#b1353fe40c5cfc1205314a4db6334f1b" title="Reconstructs heap condition after changing key value of cha externally.">changeKey</a>(<span class="keyword">const</span> T&amp; cha);
<a name="l00136"></a>00136 
<a name="l00142"></a>00142     <span class="keywordtype">bool</span> <a class="code" href="a00006.html#6c6f5bf251a2a85ebdd1a1730eb7934d" title="Checks if heap is empty.">is_empty</a>() <span class="keyword">const</span>;
<a name="l00143"></a>00143 
<a name="l00148"></a>00148     <span class="keywordtype">void</span> clear();
<a name="l00149"></a>00149 <span class="keyword">private</span>:
<a name="l00154"></a>00154     <span class="keyword">const</span> Pred&amp; prd;
<a name="l00155"></a>00155 
<a name="l00160"></a>00160     <span class="keywordtype">int</span> size;
<a name="l00161"></a>00161 
<a name="l00167"></a>00167     <span class="keywordtype">int</span> capacity;
<a name="l00168"></a>00168 
<a name="l00173"></a>00173     vector&lt;heap_node&lt;T&gt;* &gt; container;
<a name="l00174"></a>00174 
<a name="l00179"></a>00179     map&lt;T, heap_node&lt;T&gt;* &gt; heap_node_map;
<a name="l00180"></a>00180 
<a name="l00185"></a>00185     <span class="keywordtype">void</span> bubble_up(heap_node&lt;T&gt;* <span class="keyword">const</span> n);
<a name="l00186"></a>00186 
<a name="l00191"></a>00191     <span class="keywordtype">void</span> bubble_down(heap_node&lt;T&gt;* <span class="keyword">const</span> n);
<a name="l00192"></a>00192 <span class="preprocessor">#ifdef _DEBUG</span>
<a name="l00193"></a>00193 <span class="preprocessor"></span><span class="keyword">public</span>:
<a name="l00198"></a>00198     <span class="keywordtype">void</span> print_data_container();
<a name="l00199"></a>00199 <span class="preprocessor">#endif  // _DEBUG</span>
<a name="l00200"></a>00200 <span class="preprocessor"></span>};
<a name="l00201"></a>00201 
<a name="l00202"></a>00202 <span class="comment">// Implementation Begin</span>
<a name="l00203"></a>00203 
<a name="l00204"></a>00204 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00205"></a><a class="code" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd">00205</a> <a class="code" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd" title="Creates empty binary heap.">bin_heap&lt;T, Pred&gt;::bin_heap</a>(<span class="keyword">const</span> Pred&amp; prd) :
<a name="l00206"></a>00206     prd(prd), size(0), capacity(50)
<a name="l00207"></a>00207 {
<a name="l00208"></a>00208     container.resize(capacity);
<a name="l00209"></a>00209 }
<a name="l00210"></a>00210 
<a name="l00211"></a>00211 
<a name="l00212"></a>00212 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00213"></a><a class="code" href="a00006.html#b911dd559d9d9fd665b9fdf2d8202bb8">00213</a> <a class="code" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd" title="Creates empty binary heap.">bin_heap&lt;T, Pred&gt;::bin_heap</a>(<span class="keyword">const</span> Pred&amp; prd, <span class="keyword">const</span> <span class="keywordtype">int</span> est_size) :
<a name="l00214"></a>00214     prd(prd), size(0), capacity(50)
<a name="l00215"></a>00215 {
<a name="l00216"></a>00216     <span class="keywordflow">if</span> (est_size &gt; 50)
<a name="l00217"></a>00217     {
<a name="l00218"></a>00218         capacity = est_size;
<a name="l00219"></a>00219     }
<a name="l00220"></a>00220     container.resize(capacity);
<a name="l00221"></a>00221 }
<a name="l00222"></a>00222 
<a name="l00223"></a>00223 
<a name="l00224"></a>00224 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00225"></a><a class="code" href="a00006.html#19bd4241e097852ffda83b72557ffbdc">00225</a> <a class="code" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd" title="Creates empty binary heap.">bin_heap&lt;T, Pred&gt;::bin_heap</a>(<span class="keyword">const</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;</a>&amp; bh) :
<a name="l00226"></a>00226     prd(bh.prd), size(bh.size), capacity(bh.capacity)
<a name="l00227"></a>00227 {
<a name="l00228"></a>00228     container.resize(capacity);
<a name="l00229"></a>00229     <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt; size; ++i)
<a name="l00230"></a>00230     {
<a name="l00231"></a>00231         container[i] = <span class="keyword">new</span> heap_node&lt;T&gt;(bh.<a class="code" href="a00006.html#674b15241cb407c08c53e0bd21fd1dc3">container</a>[i]-&gt;data);
<a name="l00232"></a>00232     }
<a name="l00233"></a>00233 }
<a name="l00234"></a>00234 
<a name="l00235"></a>00235 
<a name="l00236"></a>00236 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00237"></a><a class="code" href="a00006.html#d31b6806316a272686015fcbf5f633cd">00237</a> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;</a>&amp; <a class="code" href="a00006.html#d31b6806316a272686015fcbf5f633cd" title="Assigns bh to this binary heap.">bin_heap&lt;T, Pred&gt;::operator=</a>(<span class="keyword">const</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;</a>&amp; bh)
<a name="l00238"></a>00238 {
<a name="l00239"></a>00239     <span class="keywordflow">if</span> (<span class="keyword">this</span> != &amp;bh)    <span class="comment">// no self assignment</span>
<a name="l00240"></a>00240     {
<a name="l00241"></a>00241         assert(&amp;prd == &amp;(bh.<a class="code" href="a00006.html#5ecc420dfd03a6a0b4c9328cac1fae14">prd</a>));
<a name="l00242"></a>00242         clear();
<a name="l00243"></a>00243         size = bh.<a class="code" href="a00006.html#8dde1008dcc24d734dbdb2c7ca50435b">size</a>;
<a name="l00244"></a>00244         capacity = bh.<a class="code" href="a00006.html#c5aa6948898bfc047cae2fe99ba28f57">capacity</a>;
<a name="l00245"></a>00245         container.resize(capacity);
<a name="l00246"></a>00246         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt; size; ++i)
<a name="l00247"></a>00247         {
<a name="l00248"></a>00248             container[i] = <span class="keyword">new</span> heap_node&lt;T&gt;(bh.<a class="code" href="a00006.html#674b15241cb407c08c53e0bd21fd1dc3">container</a>[i]-&gt;data);
<a name="l00249"></a>00249         }
<a name="l00250"></a>00250     }
<a name="l00251"></a>00251     <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00252"></a>00252 }
<a name="l00253"></a>00253 
<a name="l00254"></a>00254 
<a name="l00255"></a>00255 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00256"></a><a class="code" href="a00006.html#5283db56783a84ee28dea9d393acf905">00256</a> <a class="code" href="a00006.html#5283db56783a84ee28dea9d393acf905" title="Destructor.">bin_heap&lt;T, Pred&gt;::~bin_heap</a>()
<a name="l00257"></a>00257 {
<a name="l00258"></a>00258     clear();
<a name="l00259"></a>00259 }
<a name="l00260"></a>00260 
<a name="l00261"></a>00261 
<a name="l00262"></a>00262 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00263"></a><a class="code" href="a00006.html#6d658d61533e66cf83dce2f8e35bed17">00263</a> <span class="keywordtype">void</span> <a class="code" href="a00006.html#6d658d61533e66cf83dce2f8e35bed17" title="Inserts ins in heap.">bin_heap&lt;T, Pred&gt;::push</a>(<span class="keyword">const</span> T&amp; ins)
<a name="l00264"></a>00264 {
<a name="l00265"></a>00265     <span class="keywordflow">if</span> (size == capacity)
<a name="l00266"></a>00266     {
<a name="l00267"></a>00267          <span class="comment">// dynamic memory allocation</span>
<a name="l00268"></a>00268         capacity *= 2;
<a name="l00269"></a>00269         container.resize(capacity);
<a name="l00270"></a>00270     }
<a name="l00271"></a>00271     heap_node&lt;T&gt;* n = <span class="keyword">new</span> heap_node&lt;T&gt;(ins);
<a name="l00272"></a>00272     n-&gt;pos = size;
<a name="l00273"></a>00273     container[size] = n;
<a name="l00274"></a>00274     heap_node_map[ins] = n;
<a name="l00275"></a>00275     ++size;
<a name="l00276"></a>00276     bubble_up(n);
<a name="l00277"></a>00277 }
<a name="l00278"></a>00278 
<a name="l00279"></a>00279 
<a name="l00280"></a>00280 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00281"></a><a class="code" href="a00006.html#b463bc655b2f46cd5ff021cab28b1210">00281</a> <span class="keywordtype">void</span> <a class="code" href="a00006.html#b463bc655b2f46cd5ff021cab28b1210" title="Removes the element on top of the heap.">bin_heap&lt;T, Pred&gt;::pop</a>() 
<a name="l00282"></a>00282 {
<a name="l00283"></a>00283     assert(size &gt; 0);
<a name="l00284"></a>00284     <span class="comment">// save smallest element for return (ensured by heap condition)</span>
<a name="l00285"></a>00285     heap_node_map.erase(container[0]-&gt;data);
<a name="l00286"></a>00286     <span class="keyword">delete</span> container[0];
<a name="l00287"></a>00287     <span class="comment">// replace by last element in array and decrease heap "size"</span>
<a name="l00288"></a>00288     <span class="keywordflow">if</span> (size &gt; 1)
<a name="l00289"></a>00289     {
<a name="l00290"></a>00290         container[0] = container[--size];
<a name="l00291"></a>00291         container[0]-&gt;pos = 0;
<a name="l00292"></a>00292         <span class="comment">// reorder heap to ensure heap conditions</span>
<a name="l00293"></a>00293         bubble_down(container[0]);
<a name="l00294"></a>00294     }
<a name="l00295"></a>00295     <span class="keywordflow">else</span>
<a name="l00296"></a>00296     {
<a name="l00297"></a>00297         size = 0;
<a name="l00298"></a>00298     }
<a name="l00299"></a>00299 }
<a name="l00300"></a>00300 
<a name="l00301"></a>00301 
<a name="l00302"></a>00302 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00303"></a><a class="code" href="a00006.html#09924a9669f054bc6fdcf2dc5637f7f3">00303</a> <span class="keyword">const</span> T&amp; <a class="code" href="a00006.html#09924a9669f054bc6fdcf2dc5637f7f3" title="Returns a reference to the element at the top of the heap.">bin_heap&lt;T, Pred&gt;::top</a>()<span class="keyword"> const</span>
<a name="l00304"></a>00304 <span class="keyword"></span>{
<a name="l00305"></a>00305     <span class="keywordflow">return</span> container[0]-&gt;data;
<a name="l00306"></a>00306 }
<a name="l00307"></a>00307 
<a name="l00308"></a>00308 
<a name="l00309"></a>00309 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00310"></a><a class="code" href="a00006.html#b1353fe40c5cfc1205314a4db6334f1b">00310</a> <span class="keywordtype">void</span> <a class="code" href="a00006.html#b1353fe40c5cfc1205314a4db6334f1b" title="Reconstructs heap condition after changing key value of cha externally.">bin_heap&lt;T, Pred&gt;::changeKey</a>(<span class="keyword">const</span> T&amp; cha)
<a name="l00311"></a>00311 {
<a name="l00312"></a>00312     <span class="keywordtype">int</span> pos = heap_node_map[cha]-&gt;pos;
<a name="l00313"></a>00313     heap_node&lt;T&gt;* n = container[pos];
<a name="l00314"></a>00314     <span class="keywordflow">if</span> (pos != 0)
<a name="l00315"></a>00315     {
<a name="l00316"></a>00316         heap_node&lt;T&gt;* father = container[(pos - 1) / 2];
<a name="l00317"></a>00317         <span class="keywordflow">if</span> (prd(n-&gt;data, father-&gt;data))
<a name="l00318"></a>00318         {
<a name="l00319"></a>00319             bubble_up(n);
<a name="l00320"></a>00320             <span class="keywordflow">return</span>;
<a name="l00321"></a>00321         }
<a name="l00322"></a>00322     }
<a name="l00323"></a>00323     bubble_down(n);
<a name="l00324"></a>00324 }
<a name="l00325"></a>00325 
<a name="l00326"></a>00326 
<a name="l00327"></a>00327 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00328"></a><a class="code" href="a00006.html#6c6f5bf251a2a85ebdd1a1730eb7934d">00328</a> <span class="keywordtype">bool</span> <a class="code" href="a00006.html#6c6f5bf251a2a85ebdd1a1730eb7934d" title="Checks if heap is empty.">bin_heap&lt;T, Pred&gt;::is_empty</a>()<span class="keyword"> const</span>
<a name="l00329"></a>00329 <span class="keyword"></span>{
<a name="l00330"></a>00330     <span class="comment">// empty if if first free index is 0</span>
<a name="l00331"></a>00331     <span class="keywordflow">return</span> size == 0;
<a name="l00332"></a>00332 }
<a name="l00333"></a>00333   
<a name="l00334"></a>00334 
<a name="l00335"></a>00335 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00336"></a>00336 <span class="keywordtype">void</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;::clear</a>()
<a name="l00337"></a>00337 {
<a name="l00338"></a>00338     <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt; size; ++i)
<a name="l00339"></a>00339     {
<a name="l00340"></a>00340         <span class="keyword">delete</span> container[i];
<a name="l00341"></a>00341     }
<a name="l00342"></a>00342     size = 0;
<a name="l00343"></a>00343     heap_node_map.clear();
<a name="l00344"></a>00344 }
<a name="l00345"></a>00345 
<a name="l00346"></a>00346   
<a name="l00347"></a>00347 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00348"></a>00348 <span class="keywordtype">void</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;::bubble_up</a>(heap_node&lt;T&gt;* <span class="keyword">const</span> n)
<a name="l00349"></a>00349 {
<a name="l00350"></a>00350     <span class="keywordtype">int</span> pos = n-&gt;pos;
<a name="l00351"></a>00351     <span class="comment">// if we are not already at top AND the parent in heap is more</span>
<a name="l00352"></a>00352     <span class="keywordflow">while</span> ((pos != 0) &amp;&amp;
<a name="l00353"></a>00353            (prd(n-&gt;data, container[(pos - 1) / 2]-&gt;data)))
<a name="l00354"></a>00354     {
<a name="l00355"></a>00355         <span class="comment">// move father down</span>
<a name="l00356"></a>00356         container[pos] = container[(pos - 1) / 2];
<a name="l00357"></a>00357         container[pos]-&gt;pos = pos;
<a name="l00358"></a>00358         <span class="comment">// increment k to parent index</span>
<a name="l00359"></a>00359         pos = (pos - 1) / 2;
<a name="l00360"></a>00360     }
<a name="l00361"></a>00361     <span class="comment">// place value in its highest position in heap</span>
<a name="l00362"></a>00362     container[pos] = n;
<a name="l00363"></a>00363     container[pos]-&gt;pos = pos;
<a name="l00364"></a>00364 }
<a name="l00365"></a>00365 
<a name="l00366"></a>00366 
<a name="l00367"></a>00367 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00368"></a>00368 <span class="keywordtype">void</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;::bubble_down</a>(heap_node&lt;T&gt;* <span class="keyword">const</span> n)
<a name="l00369"></a>00369 {
<a name="l00370"></a>00370     <span class="keywordtype">int</span> pos = n-&gt;pos;
<a name="l00371"></a>00371     <span class="keywordtype">int</span> j = 0;
<a name="l00372"></a>00372     <span class="keywordflow">while</span> (pos &lt; size / 2)
<a name="l00373"></a>00373     {
<a name="l00374"></a>00374         j = 2 * pos + 1;
<a name="l00375"></a>00375         <span class="comment">// if right child is smaller than left child get right child</span>
<a name="l00376"></a>00376         <span class="keywordflow">if</span> ((j &lt; size - 1) &amp;&amp;
<a name="l00377"></a>00377             (prd(container[j + 1]-&gt;data, container[j]-&gt;data)))
<a name="l00378"></a>00378         {
<a name="l00379"></a>00379             ++j;
<a name="l00380"></a>00380         }
<a name="l00381"></a>00381         <span class="comment">// if element is less or equal than its child leave it here</span>
<a name="l00382"></a>00382         <span class="keywordflow">if</span> (!prd(container[j]-&gt;data, n-&gt;data))
<a name="l00383"></a>00383         {
<a name="l00384"></a>00384             <span class="keywordflow">break</span>;
<a name="l00385"></a>00385         }
<a name="l00386"></a>00386         <span class="comment">// else move its child up</span>
<a name="l00387"></a>00387         container[pos] = container[j];
<a name="l00388"></a>00388         container[pos]-&gt;pos = pos;
<a name="l00389"></a>00389         <span class="comment">// repeat for new position</span>
<a name="l00390"></a>00390         pos = j;
<a name="l00391"></a>00391     }
<a name="l00392"></a>00392     <span class="comment">// place element into position, where heap condition is fulfilled</span>
<a name="l00393"></a>00393     container[pos] = n;
<a name="l00394"></a>00394     container[pos]-&gt;pos = pos;
<a name="l00395"></a>00395 }
<a name="l00396"></a>00396   
<a name="l00397"></a>00397 <span class="preprocessor">#ifdef _DEBUG</span>
<a name="l00398"></a>00398 <span class="preprocessor"></span><span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
<a name="l00399"></a>00399 <span class="keywordtype">void</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;::print_data_container</a>()
<a name="l00400"></a>00400 {
<a name="l00401"></a>00401     <span class="keywordflow">if</span> (size == 0)
<a name="l00402"></a>00402     {
<a name="l00403"></a>00403         cout &lt;&lt; <span class="stringliteral">"empty"</span>;
<a name="l00404"></a>00404     }
<a name="l00405"></a>00405     <span class="keywordflow">else</span>
<a name="l00406"></a>00406     {
<a name="l00407"></a>00407         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> pos = 0; pos &lt; size; ++pos)
<a name="l00408"></a>00408         {
<a name="l00409"></a>00409             cout &lt;&lt; container[pos]-&gt;data &lt;&lt; <span class="stringliteral">" "</span>;
<a name="l00410"></a>00410         }
<a name="l00411"></a>00411     }
<a name="l00412"></a>00412     cout &lt;&lt; endl;
<a name="l00413"></a>00413 }
<a name="l00414"></a>00414 <span class="preprocessor">#endif  // _DEBUG</span>
<a name="l00415"></a>00415 <span class="preprocessor"></span>
<a name="l00416"></a>00416 <span class="comment">// Implementation End</span>
<a name="l00417"></a>00417 
<a name="l00418"></a>00418 __GTL_END_NAMESPACE
<a name="l00419"></a>00419 
<a name="l00420"></a>00420 <span class="preprocessor">#endif  // GTL_BIN_HEAP_H</span>
<a name="l00421"></a>00421 <span class="preprocessor"></span>
<a name="l00422"></a>00422 <span class="comment">//--------------------------------------------------------------------------</span>
<a name="l00423"></a>00423 <span class="comment">//   end of file</span>
<a name="l00424"></a>00424 <span class="comment">//--------------------------------------------------------------------------</span>
</pre></div>    <p class="links">
      <a href="http://www.uni-passau.de/">University of Passau</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/">FMI</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/fmi/lehrstuehle/brandenburg/">Theoretical
	Computer Science</a>
    </p>
  <div class="copyright">
      Design &copy; 2002, 2003 <a href="mailto:raitner@fmi.uni-passau.de">Marcus Raitner</a>,  University of Passau 
  </div>
</body>
</html>
